#include<stdio.h>
#include<stdlib.h>
#include <string.h>

#define XALLOC(type,size) (type *)malloc(size*sizeof(type))
#define XMEMSET(pointer,type,size) memset(pointer,0,size*sizeof(type))
#define MAXNUMBER 99999999

void Merge(int a[],int p,int q,int r)
{
	int n1=q-p+1;
	int n2=r-q;
	int *L=XALLOC(int,n1+1);
	int *R=XALLOC(int,n2+1);
	XMEMSET(L,int,n1+1);
	XMEMSET(R,int,n2+1);
	int i;
	int j;
	int k;

	for(i=0;i<n1;i++)
		L[i] = a[p+i];
	for(j=0;j<n2;j++)
		R[j]= a[q+j+1];

	L[n1]=MAXNUMBER;
	R[n2]=MAXNUMBER;

	i=0;
	j=0;
	for(k=p;k<=r;k++)
		if(L[i]<=R[j])
		{
			a[k]=L[i];
			i++;
		}
		else
		{
			a[k]=R[j];
			j++;
		}
}

/*
MERGE-SORT(A, p, r)
1 if p < r
2   then q = (p + r)/2
3        MERGE-SORT(A, p, q)
4        MERGE-SORT(A, q + 1, r)
5        MERGE(A, p, q, r)


*/
void MergeSort(int a[],int p,int r)
{
	int q;
	if(p<r)
	{
		q=(p+r)/2;
		MergeSort(a,p,q);
		MergeSort(a,q+1,r);
		Merge(a,p,q,r);
	}
}

int main() 
{ 
	int i;
	int a[12]={13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21};
	MergeSort(a,0,11);
	for(i=0;i<12;i++)
	{
		printf("%d\t",a[i]);
	}
	return 0; 
} 
